package com.wangzh.data.arithmetic.recursion;

import java.util.Arrays;

public class Test {

    //冒泡排序递归实现
    //讲一个数组从小到大排序

    static int count=0;
    public static void main(String[] args) {


//        int[] arr = {1,2,7,6,5};
        int[] arr = {3,4,5,7,6};
        bubble(arr,arr.length-1);
        System.out.println(Arrays.toString(arr));
        System.out.println(count);
    }
//优化  减少次数，记录X发生变更的交换位置
    // 3    4   5   7   6
    // 3    4   5   6   7   x=3
    // 3    4   5   6   7   x=0
    // 结束  一共三次
//
    private static void bubble2(int[] arr,int j){

        count++;
        if (j==0) {
            return;
        }
        int x=0;
        for (int i = 0; i < j; i++) {
            if (arr[i]>arr[i+1]) {
                int t = arr[i];
                arr[i] = arr[i+1];
                arr[i+1]=t;
                x=i;
            }
        }
        bubble2(arr,x);
    }

    private static void bubble(int[] arr,int j){
        count++;
        if (j==0) {
            return;
        }
        for (int i = 0; i < j; i++) {
            if (arr[i]>arr[i+1]) {
                int t = arr[i];
                arr[i] = arr[i+1];
                arr[i+1]=t;
            }
        }
        bubble(arr,j-1);
    }

}
